#include<iostream>

using namespace std;

//链表分割;
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Partition 
{
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
       struct ListNode* greathead, *greattail, *lesshead, *lesstail, *cur;
       greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
       lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                lesstail->next = cur;
                lesstail = cur;
                cur = cur->next;
            }
            else 
            {
                greattail->next = cur;
                greattail = cur;
                cur = cur->next;
            }
        }

        lesstail->next = greathead->next;
        greattail->next = nullptr;
        return lesshead->next;
    }
};


//链表回文结构:

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList 
{
public:
    bool chkPalindrome(ListNode* A) 
    {
        if(A == nullptr || A->next == nullptr)
            return false;
        
        ListNode* fast = A, *slow = A;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* cur = nullptr;
        ListNode* next = slow;
        while(slow)
        {
            next = slow->next;
            slow->next = cur;
            cur = slow;
            slow = next;
        }
        next = A;
        while(cur)
        {
            if(next->val != cur->val)
                return false;
            next = next->next;
            cur = cur->next;
        }
        return true;
    }
};

//链表相交结点

//  * Definition for singly-linked list.
//  * struct ListNode {
//  *     int val;
//  *     ListNode *next;
//  *     ListNode(int x) : val(x), next(NULL) {}
//  * };
 
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        if(headA == nullptr || headB == nullptr)
            return nullptr;
        
        ListNode* pa = headA;
        ListNode* pb = headB;
        while(pa != pb)
        {
            pa = pa == nullptr ? headB : pa->next;
            pb = pb == nullptr ? headA : pb->next;
        }

        return pa;
    }
};

